// https://www.lintcode.com/problem/lowest-common-ancestor-of-a-binary-tree/description?_from=ladder&&fromId=6
// lowest common ancestor(LCA)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    
    // bool find(TreeNode * root, TreeNode * node)
    // {
    //     if (!root) return false;
    //     if (root == node) return true;
    //     else return find(root->left, node) || find(root->right, node);
    // }
    // TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
    //     if (!root) return NULL;
    //     if (!find(root, A) || !find(root, B)) return NULL;
    //     TreeNode * left = lowestCommonAncestor(root->left, A, B); if (left) return left;
    //     TreeNode * right = lowestCommonAncestor(root->right, A, B); if (right) return right;
    //   return root;
    // }
    
    // 递归查找A和B， 找到A和B第一次在不同子树中，根节点即是LCA。
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) { //从root下去找A或者B，能找到则返回，否则返回NULL
        if (!root) return NULL;
        if (root == A || root == B) return root;
        TreeNode * left = lowestCommonAncestor(root->left, A, B);
        TreeNode * right = lowestCommonAncestor(root->right, A, B);
        if (left && right) return root;
        if (left) return left;
        return right;
    }
};